/* Author: DO HOANG HAI
 * Main.java
 *
 * Created on June 4, 2006, 8:59 PM
 *
 * Description: This project demonstrates  how to use merge sort algorithm to sort an one-dimension array 
 */

package merge;

import java.util.Scanner;
/**
 *
 * @author hai
 */
public class Main {
    
    private static int[] array={5,4,-2,-6,-98,-7};
    private static Scanner reader= new Scanner(System.in);
    /** Creates a new instance of Main */
    public Main() {
    }
    
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        
       // inputData();
        sortData();
        displayResult();
    }
     public static void inputData(){
        int ar[]=new int[20];
        System.out.println("   Enter values to be sorted, finish by -1: ");
        int index=0;
        int value=reader.nextInt();
        while (value!=-1){
            ar[index]=value;
            value=reader.nextInt();     
            index++;
        }
        array= new int[index];
        for (int i=0; i<index; i++){
            array[i]=ar[i];
        }        
        
    }
      public static void displayResult(){
        for (int index=0; index<array.length; index++)
            System.out.print("  "+ array[index]);
    }
      public static void sortData(){
          mergeSort(0, array.length-1, array);
      }
      public static void mergeSort(int start, int end, int[] ar){
          
          if (end<=start) return;
          int middle = (int)((end+start)/2);
          mergeSort(start,middle, ar);
          mergeSort(middle+1, end, ar);
          merge(start, end, ar);
      }
      
      protected static void merge(int start, int end, int[] ar){
          int middle=(end+start)/2;          
          int[] temp=new int[end-start+1];
          
          for (int i=start; i<=end; i++){              
              if (i<= middle)
                  temp[i-start]=array[i];
              else
                  temp[end-start+middle+1-i]=array[i];
          }          
         
          int begin=0;
          int last=temp.length-1;
          for (int j=start; j<=end; j++){
              if (temp[begin]<temp[last]){
                  array[j]=temp[begin];
                  begin++;
              }
              else {
                  array[j]=temp[last];
                  last--;
              }
          }
          
        
      }
      
      
      
}
